package com.tgy.algorithm.base._最大回文子串;

import java.util.Arrays;

public class _manacher {

    public static int manacher(String content) {

        if (content == null || content.length() == 0) {
            return 0;
        }

        String addDivider = addDivider(content);

        int len = addDivider.length();

        int[] nexts = new int[len];
        int maxRight = -1;
        int centerIndex = -1;


        /**
         *  [.....maxRight]
         *  当 i > maxRight 时，直接进行暴力扩
         *  当 i <= maxRight
         *     找到 关于 centerIndex对称当 i',通过 nexts[i']获取回文半径 r
         *     当 i + r  < maxRight
         *       nexts[i] = r
         *     当 i + r == maxRight
         *       从 rightIndex为maxRight往外扩
         *     当 i+ r > maxRight
         *       从 i+r - 1 与 i - r +1 暴力扩
         *
         *
         */
        int leftIndex = 0;
        int rightIndex = 0;
        char[] chars = addDivider.toCharArray();
        int maxR = 0;
        for (int i = 0; i < len; i++) {
            if (i > maxRight) {
                leftIndex = i - 1;
                rightIndex = i + 1;
            }else  {
                int r = nexts[centerIndex*2 - i];
                if (r + i < maxRight) {
                    nexts[i] = r;
                    maxR = Math.max(maxR,r);
                    continue;
                }else {
                    rightIndex = maxRight+1;
                    leftIndex = i*2 - rightIndex;
                }
            }


            while (true) {
                if (leftIndex < 0 || rightIndex >= len || chars[leftIndex] != chars[rightIndex]) {
                    break;
                }
                leftIndex--;
                rightIndex++;
            }

            int newR = rightIndex - i;
            nexts[i] = newR;
            if (rightIndex - 1 > maxRight) {
                maxRight = rightIndex - 1;
                maxR = Math.max(newR,maxR);
                centerIndex = i;
            }
        }
        System.out.println(Arrays.toString(nexts));
        return maxR - 1;
    }

    public static String addDivider(String content) {

        StringBuilder sb = new StringBuilder();
        sb.append('#');
        char[] chars = content.toCharArray();
        for (char c : chars) {
            sb.append(c);
            sb.append('#');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String content = "ababbac";
        int manacher = manacher(content);
        System.out.println(manacher);
    }
}
